package com.salim.leetcode.$980;

public class UniquePathsIII {
    public int result = 0;
    public int[][] array;
    public int blockCount = 0;
    public int startI=0;
    public int startJ=0;
    public int stepCount = 0;
    public int uniquePathsIII(int[][] grid) {
        if(grid.length==0){
            return 0;
        }
        array = grid;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(array[i][j]== -1){
                    blockCount++;
                }
                if(array[i][j]==1){
                    startI = i;
                    startJ = j;
                }
            }
        }

        stepCount = grid.length *grid[0].length - blockCount;

        boolean[][] walked = new boolean[grid.length][grid[0].length];
        loop(walked,0,startI,startJ);
        return result;
    }

    public boolean loop(boolean[][] walked,int step,int i,int j){
        if(i>=array.length || j>=array[0].length || i<0 || j<0){
            return false;
        }
        if(walked[i][j]){
            return false;
        }
        if(array[i][j]==-1){
            return false;
        }

        walked[i][j] = true;
        step++;
        if(array[i][j]==2){
            if(step==stepCount){
                result++;
            }
            return true;
        }

        if(loop(walked,step,i-1,j)){
            walked[i-1][j] = false;
        }
        if(loop(walked,step,i,j-1)){
            walked[i][j-1] = false;
        }
        if(loop(walked,step,i+1,j)){
            walked[i+1][j] = false;
        }
        if(loop(walked,step,i,j+1)){
            walked[i][j+1] = false;
        }
        walked[i][j] = false;
        return true;
    }

    public static void main(String[] args) {
        UniquePathsIII u = new UniquePathsIII();
        //i.insert(new int[][]{{1, 3},{6,9}},new int[]{2,5});
        u.uniquePathsIII(new int[][]{{1,0,0,0},{0,0,0,0},{0,0,2,-1}});
//        p.getPermutation(4,6);
    }
}
